// 题目描述
// 2218. 从栈中取出 K 个硬币的最大面值和
// 难度
// 困难
// 60
// 一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币。
// 每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里。
// 给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k ，请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少 。
//   示例 1：
// 输入：piles = [[1,100,3],[7,8,9]], k = 2
// 输出：101
// 解释：
// 上图展示了几种选择 k 个硬币的不同方法。
// 我们可以得到的最大面值为 101 。
// 示例 2：
// 输入：piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
// 输出：706
// 解释：
// 如果我们所有硬币都从最后一个栈中取，可以得到最大面值和。
//   提示：
// n == piles.length
// 1 <= n <= 1000
// 1 <= piles[i][j] <= 105
// 1 <= k <= sum(piles[i].length) <= 2000
// 通过次数6,441提交次数11,628

/**
 * @param {number[][]} piles
 * @param {number} k
 * @return {number}
 */
function maxValueOfCoins(piles, k) {
  const f = new Array(k + 1).fill(0)
  let sumN = 0
  for (const pile of piles) {
    const n = pile.length
    for (let i = 1; i < n; ++i) {
      pile[i] = pile[i] + pile[i - 1]
    }
    sumN = Math.min(sumN + n, k) // 优化：j 从前 i 个栈的大小之和开始枚举（不超过 k）
    for (let j = sumN; j > 0; --j) {
      for (let w = 0; w < Math.min(n, j); ++w) {
        f[j] = Math.max(f[j], f[j - w - 1] + pile[w]) // w 从 0 开始，物品体积为 w+1
      }
    }
  }

  return f[k]
}

console.log(
  maxValueOfCoins(
    [[72439, 85695, 81846, 42758, 65144, 14297, 31537, 39451], [19764, 71823, 36354, 46958, 28114, 87264, 15574, 87571, 48499, 65253, 12493, 74654, 51112, 77298, 1601, 76545, 59118, 53203, 22229, 76648, 48389, 74576, 27824, 75628, 94631, 70057, 96773, 19142, 80941, 34050, 27069, 39616, 56459, 78920, 41584, 53761, 17790, 58366, 24227, 34346, 22036, 44800, 81753, 99968, 82617, 6493, 78755, 74806, 53095, 98059, 7057, 10445], [34776, 2440, 79313, 55138, 11412], [97557, 18667, 41675, 50022, 11123, 17590, 83474, 54019, 35627, 13014, 37056, 77373, 91418, 41519, 76863, 15557, 27494, 14902, 45907, 54819, 12744, 82539, 58443, 25786, 51447, 35603, 69331, 2102, 47771, 93733, 34050, 54102, 23588, 28232, 8375, 65353, 98823, 59315, 90163, 45968, 72447], [89952, 10755, 71409, 74374, 84693, 90388, 28485, 66015, 12253, 38237, 70989, 62144, 18285, 8904, 39357, 99319, 37049, 75848, 46183, 1649, 29040, 71809, 86758, 11868, 65928, 25781, 52564, 25778, 16464, 99497, 5654, 65619, 19954, 53215, 45674, 69707, 13972, 78020, 52151, 52389, 33887, 13772, 92418, 664, 75634, 59765, 12688, 57722, 70461, 79363, 92026, 54512, 24041, 89916, 56759, 60123, 65610, 5850, 87097, 89258, 76416, 76776, 70034, 59027, 59023, 7240, 26813, 61778, 84256, 75049, 95050, 84324, 51091, 24696, 33869, 2910, 83693, 20924, 6863, 47022, 86839, 64209, 15103, 89342, 62669, 13559, 34788, 37247, 1159, 48940, 48692, 46709, 95576, 73397, 72163, 40122, 62845, 64454, 76710, 59387, 83344, 10579, 25225, 98674, 51953, 59175, 76545, 1637, 83613, 66988, 65439, 49451, 42592, 36905, 77702, 99501, 17782, 25256, 77296, 17769, 79030, 76171, 2491, 69504, 67000, 59663, 75582, 653, 93200, 209, 43004, 33609, 20103, 48350, 50466, 77209, 94066, 20317, 986, 82240, 1189, 63862, 96066, 66995, 57706, 6144, 20388, 35948, 62715, 36332, 73459, 74773, 35366, 12746, 37992, 15377, 14502, 8965, 53091, 7991, 59616, 81410, 24191, 30420, 18217, 94581, 72227], [15823, 59385, 68870, 56950, 33533, 2138, 11304, 35666, 97247, 54999, 5586, 79896, 69459, 57857, 28794, 58732, 58679, 44191, 90823, 59036, 75475, 60690, 10485, 10769, 17784, 19888, 80099, 99729, 19976], [59550, 50910, 17670, 26028, 25045, 98929, 99673, 89352, 75221, 57620, 65351, 98616, 78247, 97883, 54080, 42619, 82387, 23327, 91767, 43785, 66797, 66557, 58096, 85284, 84730, 80379, 80736, 66099, 95458, 26583, 37137, 3478, 95072, 63228, 3184, 71730, 89909, 24226, 90088, 80923, 13528, 75724, 63218, 74838, 27989, 18828, 89766, 4895, 31905], [22311, 14670, 33947, 26836, 29549, 28576, 37910, 93901, 80934, 56055, 60622, 35905, 45885, 359, 64145, 59122, 28757, 94294, 30261, 37745, 60919, 93941, 95291, 56083, 26328, 41586, 69373, 51571, 38224, 8198, 93813, 46157, 17867, 2827, 60845, 75333, 38851, 50012, 71241, 10619, 14825, 61706, 64996, 94305, 30241, 13894, 27289, 11738, 47231, 87766, 81880, 16220, 2854, 78683, 35109, 43632, 88767, 54656, 41975], [79264, 59527, 34943, 29393, 65145], [78117, 31420, 94376, 13668, 98867, 95735, 61876, 62952, 28389, 81260, 93529, 64178, 29771, 2738], [38084, 54888, 59209, 60068, 75301, 72449, 96921, 47727, 1566, 77534, 86174, 77797, 26250, 21817, 62066, 66740, 20896, 40867, 16346, 37595, 69693, 26361, 67906, 60877, 39891, 18658, 45460, 81337, 30870, 33636, 77290, 74525, 12125, 84153, 26825]],
    307
  )
)
